Corelab Seminar
2020-2021
Βασίλης Νάκος
Αλγόριθμοι για Μεγάλα Δεδομένα: Αποδοτικότεροι Μετασχηματισμοί Fourier και Συνελίξεις
Abstract.
Ο Γρήγορος Μετασχηματισμός Fourier (FFT), ο οποίος υπολογίζει τον διακριτό μετασχηματισμό Fourier (DFT) ενός διανύσματος μήκους n σε χρόνο O(n log n), αποτελεί μία θεμελιώδη υπολογιστική ρουτίνα, με εφαρμογές σε όλο το εύρος των θετικών επιστημών. Μεγάλο (αλλά όχι το μόνο) κομμάτι της σημαντικότητάς του έγκειται στο γεγονός ότι μέσω αυτού μπορούμε γρήγορα να υπολογίσουμε τη συνέλιξη δύο δοθέντων διανυσμάτων. Σαν εργαλεία, ο FFT και οι συνελίξεις απαντώνται από την επεξεργασία ήχου μέχρι τα οικονομικά (πχ ανάλυση χρονοσειρών για κινήσεις και συναλλαγές μετοχών), και από νευρωνικά δίκτυα μέχρι τον υπολογισμό... συντομότερων μονοπατιών σε δοθέν γράφημα.
Με την εξέλιξη της τεχνολογίας και την ανάγκη διαχείρισης δεδομένων υψηλής κλίμακας σε πληθώρα εφαρμογών, αλλά και από θεωρητικό φυσικά ενδιαφέρον, έχει προκύψει μια αρκετά εκτεταμένη γραμμή έρευνας την τελευταία εικοσαετία η οποία εστιάζει στη σχεδίαση αλγορίθμων οι οποίοι εκμεταλλεύονται δομικές πληροφορίες σχετικά με τα διανύσματα που εμφανίζονται στην εκάστοτε εφαρμογή, έτσι ώστε να υπολογίσουν γρηγορότερα συνελίξεις ή τον μετασχηματισμό Fourier. Το πιο πολυ-μελετημένο τέτοιο παράδειγμα είναι η συγκέντρωση της ενέργειας του διανύσματος εισόδου σε ένα υποσύνολο μεγέθους k << n. Με αυτή την συνθήκη, ελπίζει κανείς να μπορεί να υπολογίσει πολύ γρηγορότερα το "ενδιαφέρον" κομμάτι πληροφορίας του DFT ενός διανύσματος (ή ενός αντικειμένου γενικότερα), σε χρόνο ανάλογο της πραγματικής πολυπλοκότητας του αντικειμένου (στην προκειμένη το k), αντί σε χρόνο ανάλογο της πολυπλοκότητας του περιβάλλοντος χώρου στον οποίο το αντικείμενο ζει (στην προκείμενη το n). Προβλήματα τέτοιας φύσεως έχουν μελετηθεί αρκετά στη Θεωρία Μάθησης (αρχικά από Kushilevtz-Mansour 91) και εν συνεχεία ακόμα πιο διεξοδικά στους Υπογραμμικούς Αλγορίθμους, καθώς και σε ένα βαθμό σε Αριθμητική Ανάλυση/Υπολογιστική Άλγεβρα/ Κρυπτογραφία κλπ.
Στην ομιλία αυτή θα κάνουμε ιστορική αναδρομή πάνω στο πρόβλημα του επονομαζόμενου μετασχηματισμού αραιού Fourier (spoiler Zachos alert: η αναδρομή ξεκινάει από το ...1795) και των αραιών συνελίξεων, θα εξηγήσουμε τα βασικά μοντέλα σκιαγραφώντας τις σχέσεις με διάφορους κλάδους των μαθηματικών και αλγορίθμων, θα εξηγήσουμε την τωρινή κατανόηση του κλάδου και θα θέσουμε σύγχρονα υπολογιστικά ερωτήματα, τόσο με θεωρητικό όσο και με πρακτικό προσανατολισμό.